home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / nelson / lzhuf.c < prev    next >
C/C++ Source or Header  |  1990-06-02  |  19KB  |  653 lines
  1. /**************************************************************
  2.     lzhuf.c
  3.     written by Haruyasu Yoshizaki 1988/11/20
  4.     some minor changes 1989/04/06
  5.     comments translated by Haruhiko Okumura 1989/04/07
  6.     getbit and getbyte modified 1990/03/23 by Paul Edwards
  7.       so that they would work on machines where integers are
  8.       not necessarily 16 bits (although ANSI guarantees a
  9.       minimum of 16).  This program has compiled and run with
  10.       no errors under Turbo C 2.0, Power C, and SAS/C 4.5
  11.       (running on an IBM mainframe under MVS/XA 2.2).  Could
  12.       people please use YYYY/MM/DD date format so that everyone
  13.       in the world can know what format the date is in?
  14.     external storage of filesize changed 1990/04/18 by Paul Edwards to
  15.       Intel's "little endian" rather than a machine-dependant style so
  16.       that files produced on one machine with lzhuf can be decoded on
  17.       any other.  "little endian" style was chosen since lzhuf
  18.       originated on PC's, and therefore they should dictate the
  19.       standard.
  20.     initialization of something predicting spaces changed 1990/04/22 by
  21.       Paul Edwards so that when the compressed file is taken somewhere
  22.       else, it will decode properly, without changing ascii spaces to
  23.       ebcdic spaces.  This was done by changing the ' ' (space literal)
  24.       to 0x20 (which is the far most likely character to occur, if you
  25.       don't know what environment it will be running on.
  26.     storage of filesize modified 1990/06/02 by Mark Nelson.
  27.       When reading in the file size, I was getting sign extension
  28.       when reading in bytes greater than or equal to 0x80, which
  29.       messed everything up.
  30. **************************************************************/
  31. #include <stdio.h>
  32. #include <stdlib.h>
  33. #include <string.h>
  34. #include <ctype.h>
  35.  
  36. FILE  *infile, *outfile;
  37. static unsigned long int  textsize = 0, codesize = 0, printcount = 0;
  38. char wterr[] = "Can't write.";
  39.  
  40. static void Error(char *message)
  41. {
  42.     fprintf(stderr,"\n%s\n", message);
  43.     exit(EXIT_FAILURE);
  44. }
  45.  
  46. /********** LZSS compression **********/
  47.  
  48. #define N       4096    /* buffer size */
  49. #define F       60  /* lookahead buffer size */
  50. #define THRESHOLD   2
  51. #define NIL     N   /* leaf of tree */
  52.  
  53. unsigned char
  54.         text_buf[N + F - 1];
  55. static int     match_position, match_length,
  56.         lson[N + 1], rson[N + 257], dad[N + 1];
  57.  
  58. static void InitTree(void)  /* initialize trees */
  59. {
  60.     int  i;
  61.  
  62.     for (i = N + 1; i <= N + 256; i++)
  63.         rson[i] = NIL;        /* root */
  64.     for (i = 0; i < N; i++)
  65.         dad[i] = NIL;         /* node */
  66. }
  67.  
  68. static void InsertNode(int r)  /* insert to tree */
  69. {
  70.     int  i, p, cmp;
  71.     unsigned char  *key;
  72.     unsigned c;
  73.  
  74.     cmp = 1;
  75.     key = &text_buf[r];
  76.     p = N + 1 + key[0];
  77.     rson[r] = lson[r] = NIL;
  78.     match_length = 0;
  79.     for ( ; ; ) {
  80.         if (cmp >= 0) {
  81.             if (rson[p] != NIL)
  82.                 p = rson[p];
  83.             else {
  84.                 rson[p] = r;
  85.                 dad[r] = p;
  86.                 return;
  87.             }
  88.         } else {
  89.             if (lson[p] != NIL)
  90.                 p = lson[p];
  91.             else {
  92.                 lson[p] = r;
  93.                 dad[r] = p;
  94.                 return;
  95.             }
  96.         }
  97.         for (i = 1; i < F; i++)
  98.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  99.                 break;
  100.         if (i > THRESHOLD) {
  101.             if (i > match_length) {
  102.                 match_position = ((r - p) & (N - 1)) - 1;
  103.                 if ((match_length = i) >= F)
  104.                     break;
  105.             }
  106.             if (i == match_length) {
  107.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  108.                     match_position = c;
  109.                 }
  110.             }
  111.         }
  112.     }
  113.     dad[r] = dad[p];
  114.     lson[r] = lson[p];
  115.     rson[r] = rson[p];
  116.     dad[lson[p]] = r;
  117.     dad[rson[p]] = r;
  118.     if (rson[dad[p]] == p)
  119.         rson[dad[p]] = r;
  120.     else
  121.         lson[dad[p]] = r;
  122.     dad[p] = NIL; /* remove p */
  123. }
  124.  
  125. static void DeleteNode(int p)  /* remove from tree */
  126. {
  127.     int  q;
  128.  
  129.     if (dad[p] == NIL)
  130.         return;         /* not registered */
  131.     if (rson[p] == NIL)
  132.         q = lson[p];
  133.     else
  134.     if (lson[p] == NIL)
  135.         q = rson[p];
  136.     else {
  137.         q = lson[p];
  138.         if (rson[q] != NIL) {
  139.             do {
  140.                 q = rson[q];
  141.             } while (rson[q] != NIL);
  142.             rson[dad[q]] = lson[q];
  143.             dad[lson[q]] = dad[q];
  144.             lson[q] = lson[p];
  145.             dad[lson[p]] = q;
  146.         }
  147.         rson[q] = rson[p];
  148.         dad[rson[p]] = q;
  149.     }
  150.     dad[q] = dad[p];
  151.     if (rson[dad[p]] == p)
  152.         rson[dad[p]] = q;
  153.     else
  154.         lson[dad[p]] = q;
  155.     dad[p] = NIL;
  156. }
  157.  
  158. /* Huffman coding */
  159.  
  160. #define N_CHAR      (256 - THRESHOLD + F)
  161.                 /* kinds of characters (character code = 0..N_CHAR-1) */
  162. #define T       (N_CHAR * 2 - 1)    /* size of table */
  163. #define R       (T - 1)         /* position of root */
  164. #define MAX_FREQ    0x8000      /* updates tree when the */
  165.                     /* root frequency comes to this value. */
  166.  
  167. typedef unsigned char uchar;
  168.  
  169.  
  170. /* table for encoding and decoding the upper 6 bits of position */
  171.  
  172. /* for encoding */
  173. uchar p_len[64] = {
  174.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  175.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  176.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  177.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  178.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  179.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  180.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  181.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  182. };
  183. uchar p_code[64] = {
  184.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  185.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  186.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  187.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  188.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  189.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  190.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  191.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  192. };
  193.  
  194. /* for decoding */
  195. uchar d_code[256] = {
  196.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  197.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  198.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  199.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  200.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  201.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  202.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  203.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  204.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  205.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  206.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  207.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  208.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  209.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  210.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  211.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  212.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  213.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  214.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  215.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  216.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  217.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  218.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  219.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  220.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  221.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  222.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  223.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  224.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  225.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  226.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  227.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  228. };
  229.  
  230. uchar d_len[256] = {
  231.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  232.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  233.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  234.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  235.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  236.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  237.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  238.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  239.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  240.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  241.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  242.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  243.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  244.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  245.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  246.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  247.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  248.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  249.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  250.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  251.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  252.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  253.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  254.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  255.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  256.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  257.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  258.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  259.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  260.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  261.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  262.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  263. };
  264.  
  265. unsigned freq[T + 1]; /* frequency table */
  266.  
  267. int prnt[T + N_CHAR]; /* pointers to parent nodes, except for the */
  268.             /* elements [T..T + N_CHAR - 1] which are used to get */
  269.             /* the positions of leaves corresponding to the codes. */
  270.  
  271. int son[T];   /* pointers to child nodes (son[], son[] + 1) */
  272.  
  273. unsigned getbuf = 0;
  274. uchar getlen = 0;
  275.  
  276. static int GetBit(void)    /* get one bit */
  277. {
  278.     unsigned i;
  279.  
  280.     while (getlen <= 8) {
  281.         if ((int)(i = getc(infile)) < 0) i = 0;
  282.         getbuf |= i << (8 - getlen);
  283.         getlen += 8;
  284.     }
  285.     i = getbuf;
  286.     getbuf <<= 1;
  287.     getlen--;
  288.     return (int)((i & 0x8000) >> 15);
  289. }
  290.  
  291. static int GetByte(void)   /* get one byte */
  292. {
  293.     unsigned i;
  294.  
  295.     while (getlen <= 8) {
  296.         if ((int)(i = getc(infile)) < 0) i = 0;
  297.         getbuf |= i << (8 - getlen);
  298.         getlen += 8;
  299.     }
  300.     i = getbuf;
  301.     getbuf <<= 8;
  302.     getlen -= 8;
  303.     return (int)((i & 0xff00) >> 8);
  304. }
  305.  
  306. unsigned putbuf = 0;
  307. uchar putlen = 0;
  308.  
  309. static void Putcode(int l, unsigned c)     /* output c bits of code */
  310. {
  311.     putbuf |= c >> putlen;
  312.     if ((putlen += l) >= 8) {
  313.         if (putc(putbuf >> 8, outfile) == EOF) {
  314.             Error(wterr);
  315.         }
  316.         if ((putlen -= 8) >= 8) {
  317.             if (putc(putbuf, outfile) == EOF) {
  318.                Error(wterr);
  319.             }
  320.             codesize += 2;
  321.             putlen -= 8;
  322.             putbuf = c << (l - putlen);
  323.         } else {
  324.             putbuf <<= 8;
  325.             codesize++;
  326.         }
  327.     }
  328. }
  329.  
  330.  
  331. /* initialization of tree */
  332.  
  333. static void StartHuff(void)
  334. {
  335.     int i, j;
  336.  
  337.     for (i = 0; i < N_CHAR; i++) {
  338.         freq[i] = 1;
  339.         son[i] = i + T;
  340.         prnt[i + T] = i;
  341.     }
  342.     i = 0; j = N_CHAR;
  343.     while (j <= R) {
  344.         freq[j] = freq[i] + freq[i + 1];
  345.         son[j] = i;
  346.         prnt[i] = prnt[i + 1] = j;
  347.         i += 2; j++;
  348.     }
  349.     freq[T] = 0xffff;
  350.     prnt[R] = 0;
  351. }
  352.  
  353.  
  354. /* reconstruction of tree */
  355.  
  356. static void reconst(void)
  357. {
  358.     int i, j, k;
  359.     unsigned f, l;
  360.  
  361.     /* collect leaf nodes in the first half of the table */
  362.     /* and replace the freq by (freq + 1) / 2. */
  363.     j = 0;
  364.     for (i = 0; i < T; i++) {
  365.         if (son[i] >= T) {
  366.             freq[j] = (freq[i] + 1) / 2;
  367.             son[j] = son[i];
  368.             j++;
  369.         }
  370.     }
  371.     /* begin constructing tree by connecting sons */
  372.     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  373.         k = i + 1;
  374.         f = freq[j] = freq[i] + freq[k];
  375.         for (k = j - 1; f < freq[k]; k--);
  376.         k++;
  377.         l = (j - k) * 2;
  378.         memmove(&freq[k + 1], &freq[k], l);
  379.         freq[k] = f;
  380.         memmove(&son[k + 1], &son[k], l);
  381.         son[k] = i;
  382.     }
  383.     /* connect prnt */
  384.     for (i = 0; i < T; i++) {
  385.         if ((k = son[i]) >= T) {
  386.             prnt[k] = i;
  387.         } else {
  388.             prnt[k] = prnt[k + 1] = i;
  389.         }
  390.     }
  391. }
  392.  
  393.  
  394. /* increment frequency of given code by one, and update tree */
  395. static void update(int c)
  396. {
  397.     int i, j, k, l;
  398.  
  399.     if (freq[R] == MAX_FREQ) {
  400.         reconst();
  401.     }
  402.     c = prnt[c + T];
  403.     do {
  404.         k = ++freq[c];
  405.  
  406.         /* if the order is disturbed, exchange nodes */
  407.         if (k > freq[l = c + 1]) {
  408.             while (k > freq[++l]);
  409.             l--;
  410.             freq[c] = freq[l];
  411.             freq[l] = k;
  412.  
  413.             i = son[c];
  414.             prnt[i] = l;
  415.             if (i < T) prnt[i + 1] = l;
  416.  
  417.             j = son[l];
  418.             son[l] = i;
  419.  
  420.             prnt[j] = c;
  421.             if (j < T) prnt[j + 1] = c;
  422.             son[c] = j;
  423.  
  424.             c = l;
  425.         }
  426.     } while ((c = prnt[c]) != 0); /* repeat up to root */
  427. }
  428. unsigned code, len;
  429.  
  430. static void EncodeChar(unsigned c)
  431. {
  432.     unsigned i;
  433.     int j, k;
  434.  
  435.     i = 0;
  436.     j = 0;
  437.     k = prnt[c + T];
  438.  
  439.     /* travel from leaf to root */
  440.     do {
  441.         i >>= 1;
  442.  
  443.         /* if node's address is odd-numbered, choose bigger brother node */
  444.         if (k & 1) i += 0x8000;
  445.  
  446.         j++;
  447.     } while ((k = prnt[k]) != R);
  448.     Putcode(j, i);
  449.     code = i;
  450.     len = j;
  451.     update(c);
  452. }
  453.  
  454. static void EncodePosition(unsigned c)
  455. {
  456.     unsigned i;
  457.  
  458.     /* output upper 6 bits by table lookup */
  459.     i = c >> 6;
  460.     Putcode(p_len[i], (unsigned)p_code[i] << 8);
  461.     /* output lower 6 bits verbatim */
  462.     Putcode(6, (c & 0x3f) << 10);
  463. }
  464.  
  465. static void EncodeEnd(void)
  466. {
  467.     if (putlen) {
  468.         if (putc(putbuf >> 8, outfile) == EOF) {
  469.             Error(wterr);
  470.         }
  471.         codesize++;
  472.     }
  473. }
  474.  
  475. static int DecodeChar(void)
  476. {
  477.    unsigned c;
  478.  
  479.     c = son[R];
  480.  
  481.     /* travel from root to leaf, */
  482.     /* choosing the smaller child node (son[]) if the read bit is 0, */
  483.     /* the bigger (son[]+1} if 1 */
  484.     while (c < T) {
  485.         c += GetBit();
  486.         c = son[c];
  487.  
  488.     }
  489.     c -= T;
  490.     update(c);
  491.     return (int)c;
  492. }
  493.  
  494. static int DecodePosition(void)
  495. {
  496.     unsigned i, j, c;
  497.  
  498.     /* recover upper 6 bits from table */
  499.     i = GetByte();
  500.     c = (unsigned)d_code[i] << 6;
  501.     j = d_len[i];
  502.  
  503.     /* read lower 6 bits verbatim */
  504.     j -= 2;
  505.     while (j--) {
  506.         i = (i << 1) + GetBit();
  507.     }
  508.     return (int)(c | (i & 0x3f));
  509. }
  510.  
  511. /* compression */
  512.  
  513. static void Encode(void)  /* compression */
  514. {
  515.     int  i, c, len, r, s, last_match_length;
  516.  
  517.     fseek(infile, 0L, 2);
  518.     textsize = ftell(infile);
  519.     fputc((int)((textsize & 0xff000000L) >> 24),outfile);
  520.     fputc((int)((textsize & 0xff0000L) >> 16),outfile);
  521.     fputc((int)((textsize & 0xff00) >> 8),outfile);
  522.     fputc((int)((textsize & 0xff)),outfile);
  523.     if (ferror(outfile))
  524.         Error(wterr);   /* output size of text */
  525.     if (textsize == 0)
  526.         return;
  527.     rewind(infile);
  528.     textsize = 0;           /* rewind and re-read */
  529.     StartHuff();
  530.     InitTree();
  531.     s = 0;
  532.     r = N - F;
  533.     for (i = s; i < r; i++)
  534.         text_buf[i] = 0x20;
  535.     for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  536.         text_buf[r + len] = c;
  537.     textsize = len;
  538.     for (i = 1; i <= F; i++)
  539.         InsertNode(r - i);
  540.     InsertNode(r);
  541.     do {
  542.         if (match_length > len)
  543.             match_length = len;
  544.         if (match_length <= THRESHOLD) {
  545.             match_length = 1;
  546.             EncodeChar(text_buf[r]);
  547.         } else {
  548.             EncodeChar(255 - THRESHOLD + match_length);
  549.             EncodePosition(match_position);
  550.         }
  551.         last_match_length = match_length;
  552.         for (i = 0; i < last_match_length &&
  553.                 (c = getc(infile)) != EOF; i++) {
  554.             DeleteNode(s);
  555.             text_buf[s] = c;
  556.             if (s < F - 1)
  557.                 text_buf[s + N] = c;
  558.             s = (s + 1) & (N - 1);
  559.             r = (r + 1) & (N - 1);
  560.             InsertNode(r);
  561.         }
  562.         if ((textsize += i) > printcount) {
  563.             fprintf(stderr,"%12ld\r", textsize);
  564.             printcount += 1024;
  565.         }
  566.         while (i++ < last_match_length) {
  567.             DeleteNode(s);
  568.             s = (s + 1) & (N - 1);
  569.             r = (r + 1) & (N - 1);
  570.             if (--len) InsertNode(r);
  571.         }
  572.     } while (len > 0);
  573.     EncodeEnd();
  574.     printf("In : %ld bytes\n", textsize);
  575.     printf("Out: %ld bytes\n", codesize);
  576.     printf("Out/In: %.3f\n", (double)codesize / textsize);
  577. }
  578.  
  579. static void Decode(void)  /* recover */
  580. {
  581.     int  i, j, k, r, c;
  582.     unsigned long int  count;
  583.  
  584.     textsize = (unsigned char) fgetc(infile);
  585.     textsize <<= 8;
  586.     textsize |= (unsigned char) fgetc(infile);
  587.     textsize <<= 8;
  588.     textsize |= (unsigned char) fgetc(infile);
  589.     textsize <<= 8;
  590.     textsize |= (unsigned char) fgetc(infile);
  591.     fprintf( stderr, "Text size = %ld\n", textsize );
  592.     if (ferror(infile))
  593.         Error("Can't read");  /* read size of text */
  594.     if (textsize == 0)
  595.         return;
  596.     StartHuff();
  597.     for (i = 0; i < N - F; i++)
  598.         text_buf[i] = 0x20;
  599.     r = N - F;
  600.     for (count = 0; count < textsize; ) {
  601.         c = DecodeChar();
  602.         if (c < 256) {
  603.             if (putc(c, outfile) == EOF) {
  604.                 Error(wterr);
  605.             }
  606.             text_buf[r++] = c;
  607.             r &= (N - 1);
  608.             count++;
  609.         } else {
  610.             i = (r - DecodePosition() - 1) & (N - 1);
  611.             j = c - 255 + THRESHOLD;
  612.             for (k = 0; k < j; k++) {
  613.                 c = text_buf[(i + k) & (N - 1)];
  614.                 if (putc(c, outfile) == EOF) {
  615.                     Error(wterr);
  616.                 }
  617.                 text_buf[r++] = c;
  618.                 r &= (N - 1);
  619.                 count++;
  620.             }
  621.         }
  622.         if (count > printcount) {
  623.             fprintf(stderr,"%12ld\r", count);
  624.             printcount += 1024;
  625.         }
  626.     }
  627.     fprintf(stderr,"%12ld\n", count);
  628. }
  629.  
  630. int main(int argc, char *argv[])
  631. {
  632.     char  *s;
  633.  
  634.     if (argc != 4) {
  635.         printf("'lzhuf e file1 file2' encodes file1 into file2.\n"
  636.                "'lzhuf d file2 file1' decodes file2 into file1.\n");
  637.         return EXIT_FAILURE;
  638.     }
  639.     if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  640.      || (s = argv[2], (infile = fopen(s, "rb")) == NULL)
  641.      || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  642.         printf("??? %s\n", s);
  643.         return EXIT_FAILURE;
  644.     }
  645.     if (toupper(*argv[1]) == 'E')
  646.         Encode();
  647.     else
  648.         Decode();
  649.     fclose(infile);
  650.     fclose(outfile);
  651.     return EXIT_SUCCESS;
  652. }
  653.